package unionfindset;

import java.util.Arrays;

public class UnionFindSet {
    public int[] elem;

    public UnionFindSet(int n) {
        this.elem = new int[n];
        Arrays.fill(elem,-1);
    }
    //查询数据x的根节点
    public int findRoot(int x){
        if(x<0){
            throw new IndexOutOfBoundsException("下标不合法,是负数");
        }
        while(elem[x]>=0){
            x=elem[x];
        }
        return x;
    }
    //查询x1和x2是不是同一个集合
    public boolean isSameUnionFindSet(int x1,int x2){
        int index1=findRoot(x1);
        int index2=findRoot(x2);
        if(index1==index2){
            return true;
        }
        return false;
    }
    //合并（合并的是根节点）
    public void union(int x1,int x2){
        //分别找到各自的根节点
        int index1=findRoot(x1);
        int index2=findRoot(x2);
        //同一个集合 不用合并
        if(index1==index2){
            return;
        }
        //合并
        elem[index1]=elem[index1]+elem[index2];//更新孩子的数量
        elem[index2]=index1;//更新另一棵树的根节点
    }
    //统计当前集合中有多少个元素
    public int getCount(){
        int count=0;
        for (int x : elem) {
            if(x<0){
                count++;
            }
        }
        return count;
    }
    public void print(){
        for (int x : elem) {
            System.out.print(x+" ");
        }
    }
}
